
import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 }
public class TextDemo {
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if(root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode head = stack.pop();
            list.add(head.val);
            if(head.right!=null){
                stack.push(head.right);
            }
            if(head.left!=null){
                stack.push(head.left);
            }

        }
        return list;


    }
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(!stack.isEmpty()||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode head = stack1.pop();
            stack2.push(head);
            if(head.left!=null){
                stack1.push(head.left);
            }

            if(head.right!=null){
                stack1.push(head.right);
            }
        }
        while(!stack2.isEmpty()){
            list.add(stack2.pop().val);
        }
        return list;

    }


    public static int[][] threeOrders (TreeNode root) {
        // write code here

        //先序遍历
        List<Integer> list1 = new ArrayList<>();
        list1 =  preorderTraversal(root);
        //中序
        List<Integer> list2 = new ArrayList<>();
        list2 = inorderTraversal(root);
        //后续
        List<Integer> list3 = new ArrayList<>();
        list2 =postorderTraversal(root);

        int[][] res=new int[3][list1.size()];
        for(int i=0;i<list1.size();i++){
            res[0][i]=list1.get(i);
            res[1][i]=list2.get(i);
            res[2][i]=list3.get(i);

        }
        return res;

    }

    public static void main(String[] args) {
        threeOrders(null);
    }

}
